/** 并查集相关算法
 * 1.Quick-find:通过染色，最野蛮、最慢
 * 2.Quick-Union：只记录每一个节点的父节点的树.find的时间复杂度增加了，但是merge的时间复杂度降低
 * 3.Weighted Quick-Union:并查集按质合并
 * 4.路径压缩算法
 */


class QuickFind {
    constructor(n) {
        this.n = n;
        this.colors = new Array(n).fill(0).map((_v, index) => index); // 用颜色表示
    }
    find(x) {
        return this.colors[x]
    }
    merge(x, y) {
        if (this.colors[x] == this.colors[y]) return;
        const cx = this.colors[x];
        const cy = this.colors[y];
        for (var i = 0;i<this.n;i++) {
            if (this.colors[i] == cx) {
                this.colors[i] = cy;
            }
        }
    }
    same(x, y) {
        return this.colors[x] == this.colors[y]
    }
}

const quickFind = new QuickFind(19);
[[1,3], [3, 5], [2, 5], [7, 8]].map(item => quickFind.merge(...item))
console.info(quickFind.same(5, 1))

class QuickUnion {
    constructor(n) {
        this.n = n;
        this.father = [];
        for (var i = 0;i<n;i++) {
            this.father[i] = i; // 当前每一个节点的父节点是他自己
         }
    }
    find(x) {
        if (this.father[x] === x) return x; // 自己是自己的根节点
        return this.find(this.father[x]);
    }
    /** 降低了合并操作的时间复杂度 */
    merge(x, y) {
        const fx = this.find(x);
        const fy = this.find(y);
        if (fx == fy) return;
        this.father[x] = fy;
    }
    same(x, y) {
        const fx = this.find(x);
        const fy = this.find(y);
        return fx == fy;
    }
}

const quickUnion = new QuickUnion(19);
[[1,3], [3, 5], [2, 5], [7, 8]].map(item => quickUnion.merge(...item))
console.info(quickUnion.same(5, 1))

class WeightedQuickUnion {
    constructor(n) {
        this.n = n;
        this.father = [];
        this.size = [] // 记录当前节点树，多少个节点
        for (var i = 0;i<n;i++) {
            this.father[i] = i;
            this.size[i] = 1;
        }
    } 
    /** 最终找到的是当前这个树的根节点 */
    find(x) {
        if(this.father[x] == x) return x;
        return this.find(this.father[x])
    }
    merge(x, y) {
        const fx = this.find(x);
        const fy = this.find(y);
        if(fx == fy) return;
        //  节点数少的当作子节点，挂载在父亲节点上
        if (this.size[fx] < this.size[fy]) {
            this.father[fx] = fy;
            this.size[fy] += this.size[fx]
        } else {
            this.father[fy] = fx;
            this.size[fx] += this.size[fy]
        }
    }
    same(x, y) {
        const fx = this.find(x);
        const fy = this.find(y);
        return fx == fy;
    }
}

const weightedQuickUnion = new WeightedQuickUnion(19);
[[1,3], [3, 5], [2, 5], [7, 8]].map(item => weightedQuickUnion.merge(...item))
console.info(weightedQuickUnion.same(5, 1))


/** 路径压缩，最优解 */
class UnionFind {
    constructor(n) {
        this.n = n;
        this.father = [];
        for(var i = 0;i<n;i++) {
            this.father[i] = i;
        }
    }
    /** 压缩路径的重要操作！！！！！ */
    find(x) {
        if(this.father[x] == x) return x;
        const root = this.find(this.father[x])
        this.father[x] = root;
        return root;
    }
    merge(x, y) {
        const fx = this.find(x);
        const fy = this.find(y);
        if(fx == fy) return;
        this.father[fx] = fy;
    }
    same(x, y) {
        const fx = this.find(x);
        const fy = this.find(y);
        return fx == fy;
    }
}


const unionFind = new UnionFind(19);
[[1,3], [3, 5], [2, 5], [7, 8]].map(item => unionFind.merge(...item))
console.info(unionFind.same(5, 1))

